import java.util.List;

/**
* Connect 4  Demo by Yngvi Bjornsson
*/

public class Search {
    private Move bestMove = null;
    private int max = Integer.MIN_VALUE;
    private int depth = 6;
   

    /**
    * Method to get the level of depth of the min-max
    * @return depth
    */
    public int getDepth() {
        return depth;
    }

    /**
    * Method to set the level of depth of the min-max
    * @param depth
    */
    public void setDepth(int depth) {
        this.depth = depth;
    }

    /**
    * Method to find the best move considering the current state
    * @param state
    * @param depth
    * @return
    */
    public Move findBestMove( State state, int depth )
    {
        /*
        implement this function. Remove the code below, this
        is only for demonstration and testing. It selects an almost
        random move.
        */
        setDepth(depth);
        return alphaBeta(state);
    }
   
    /**
    * The first interaction is different for the root
    * @param state
    * @param alpha
    * @param beta
    * @return
    */
    private int maxValueRoot(State state, int alpha, int beta){
        if ((state.isTerminal()) || (depth == 0))
            return state.getEvaluation();   
   
        int v = Integer.MIN_VALUE;
        for (Move move : state.getActions()){
            state.make(move);
            depth--;
            v = Math.max(v, minValue(state, alpha, beta));
            state.retract(move);
            depth++;
       
            if (v > this.max){
                this.max = v;
                this.bestMove = move;
            }
           
            if (v >= beta)
                return v;
            alpha = Math.max(alpha, v);
        }
        return v;
     
    }
   
    /**
    * Compute the value of the max
    * @param state
    * @param alpha
    * @param beta
    * @return
    */
    private int maxValue(State state, int alpha, int beta){
        if ((state.isTerminal())|| (depth == 0))
            return state.getEvaluation();   
   
        int v = Integer.MIN_VALUE;
        for (Move move : state.getActions()){
            state.make(move);
            depth--;
            v = Math.max(v, minValue(state, alpha, beta));
            state.retract(move);
            depth++;
           
            if (v >= beta)
                return v;
            alpha = Math.max(alpha, v);
        }
        return v;
     
    }
   
   
   
    /**
    * Compute the value of the min
    * @param state
    * @param alpha
    * @param beta
    * @return
    */
    private int minValue(State state, int alpha, int beta){
        if (state.isTerminal())
            return state.getEvaluation();   
   
        int v = Integer.MAX_VALUE;
        for (Move move : state.getActions()){
            state.make(move);
            depth--;
            v = Math.min(v, maxValue(state, alpha, beta));
            state.retract(move);
            depth++;
            if (v <= alpha)
                return v;
            beta = Math.min(beta, v);
        }
        return v;
    }
   
    /**
    * Implementation of the alpha-beta algorithm
    * @param state
    * @return
    */
    private Move alphaBeta(State state){
        maxValueRoot(state, Integer.MAX_VALUE*-1, Integer.MAX_VALUE);
        return this.bestMove;

    }


}